#include <iostream>
using namespace std;
class Solution {
public:
    int waysToStep(int n) {
        if(n < 3) return n;
        int base = 1e9+7;
        // 初始化
        // d[0]=1 ({1})
        // d[1]=2 ({1,1}, {2})
        // d[2]=4 ({1,1,1}, {2,1}, {1,2}, {3})
        int dp0 = 1,dp1 = 2,dp2 = 4;
        int temp1,temp2;
        while(n > 3)
        {
            temp1 = dp1;
            temp2 = dp2;
            dp2 = ((dp0 + dp1) % base + dp2) % base;
            dp0 = temp1;
            dp1 = temp2;
            --n;
        }
        return dp2;
    }
};

int main()
{
    return 0;
}